package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:实现函数 int sqrt(int x).
 * 计算并返回 x 的平方根（向下取整）
 * User:yxd
 * Date:2022-01-13
 * Time:22:39
 */
public class NC32 {
    public static void main(String[] args) {
        int x = 2143195649;
        System.out.println(sqrt(x));
    }
    public static int sqrt(int x) {
        // write code here
        if(x == 1) return 1;
        int left = 1,right = x; //左右边界
        while(right >= left){
            int mid = (right + left) / 2;  //中间值
            if(mid <= x / mid && (mid + 1) > x / (mid + 1)) return mid; // mid*mid可能溢出，所以用除法
            if(mid > x / mid) right = mid -1;
            else  left = mid +1;
        }
        return 0;
    }
    public  static int sqrt1 (int x) {
        // write code here
        if(x==1) return 1;
        int l = 0;

        while(l <= x){
            if(l * l == x){
                return l;
            }
            if(l * l > x){
                return l - 1 ;
            }
            l++;

        }
        return l ;
    }
}
